package source.linklist;

import org.junit.Test;

import java.util.HashSet;

public class LinkList {
    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }

        ListNode() {
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 环形链表
     * <p>
     * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
     * 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
     * 注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
     * <p>
     * 解法一： hash表
     *
     * @param head 给你一个链表的头节点 head ，判断链表中是否有环。
     * @return 如果链表中存在环 ，则返回 true 。 否则，返回 false 。
     */
    public boolean hasCycle(ListNode head) {
        HashSet<ListNode> hashSet = new HashSet<>();
        while (head != null) {
            if (hashSet.contains(head))
                return true;
            hashSet.add(head);
            head = head.next;
        }
        return false;
    }

    /**
     * 解法二： 快慢指针
     *
     * @param head 链表
     * @return 是否有环路
     */
    public boolean hasCycle2(ListNode head) {
        if (head == null || head.next == null)
            return false;
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null)
                return false;
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }

    /**
     * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
     * 请你将两个数相加，并以相同形式返回一个表示和的链表。
     * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     *
     * @param l1 l1 = [9,9,9,9,9,9,9],
     * @param l2 l2 = [9,9,9,9]
     * @return [8, 9, 9, 9, 0, 0, 0, 1]
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null;
        ListNode last = null;
        int grade = 0;
        while (l1 != null || l2 != null || grade != 0) {
            int sum = grade;
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            if (sum / 10 == 1) grade = 1;
            else grade = 0;
            ListNode currentNode = new ListNode(sum % 10, null);

            if (last == null) head = currentNode;
            else last.next = currentNode;

            last = currentNode;
        }
        return head;
    }


    @Test
    public void test() {
        StringBuilder stringBuilder = new StringBuilder("ab");
        char c = stringBuilder.charAt(0);
        int i = Integer.parseInt(String.valueOf(stringBuilder.charAt(0)));
        char[] charArray = stringBuilder.toString().toCharArray();

        System.out.println(stringBuilder.reverse());
    }

    /**
     * 合并两个有序链表
     * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
     *
     * @param list1 l1 = [1,2,4],
     * @param list2 l2 = [1,3,4]
     * @return [1, 1, 2, 3, 4, 4]
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head = null;
        ListNode last = null;
        while (list1 != null && list2 != null) {
            if (list1.val >= list2.val) {
                if (head == null) {
                    head = new ListNode(list2.val, null);
                    last = head;
                } else {
                    last.next = new ListNode(list2.val, null);
                    last = last.next;
                }
                list2 = list2.next;
            } else {
                if (head == null) {
                    head = new ListNode(list1.val, null);
                    last = head;
                } else {
                    last.next = new ListNode(list1.val, null);
                    last = last.next;
                }
                list1 = list1.next;
            }
        }
        while (list1 != null) {
            if (head == null) {
                head = new ListNode(list1.val, null);
                last = head;
            } else {
                last.next = new ListNode(list1.val, null);
                last = last.next;
            }
            list1 = list1.next;
        }
        while (list2 != null) {
            if (head == null) {
                head = new ListNode(list2.val, null);
                last = head;
            } else {
                last.next = new ListNode(list2.val, null);
                last = last.next;
            }
            list2 = list2.next;
        }
        return head;
    }

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    /**
     * 随机链表的复制
     * <p>
     * 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
     * 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。
     * 新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。
     * 复制链表中的指针都不应指向原链表中的节点 。
     * 例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。
     * 那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
     * 返回复制链表的头节点。
     * 用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
     * val：一个表示 Node.val 的整数。
     * random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。
     * 你的代码 只 接受原链表的头节点 head 作为传入参数。
     *
     * @param head 链表头指针
     * @return 新链表头指针
     */
    public Node copyRandomList(Node head) {
        if (head == null)
            return null;
        Node newNode;
        for (Node node = head; node != null; node = node.next.next) {
            newNode = new Node(node.val);
            newNode.next = node.next;
            node.next = newNode;
        }
        for (Node node = head; node != null; node = node.next.next) {
            newNode = node.next;
            newNode.random = (node.random == null) ? null : node.random.next;
        }
        Node newHead = head.next;
        for (Node node = head; node != null; node = node.next) {
            newNode = node.next;
            node.next = newNode.next;
            newNode.next = node.next == null ? null : node.next.next;
        }
        return newHead;
    }

    /**
     * 反转链表II
     * <p>
     * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。
     * 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
     *
     * @param head  head = [1,2,3,4,5],
     * @param left  left = 2,
     * @param right right = 4
     * @return [1, 4, 3, 2, 5]
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        while (left <= right) {
            int i = 1;
            ListNode lNode = head;
            while (i < left) {
                lNode = lNode.next;
                i++;
            }
            ListNode rNode = lNode;
            while (i < right) {
                rNode = rNode.next;
                i++;
            }
            int value = lNode.val;
            lNode.val = rNode.val;
            rNode.val = value;
            left++;
            right--;
        }
        return head;
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode hair = new ListNode(0, head);
        ListNode pre = hair;
        while (head != null) {
            ListNode tail = pre;
            for (int i = 0; i < k; i++) {
                tail = tail.next;
                if (tail == null)
                    return hair.next;
            }
            ListNode nex = tail.next;
            // 翻转
            ListNode[] listNodes = myReverse(head, tail);
            pre.next = listNodes[0];
            listNodes[1].next = nex;
            head = nex;
            pre = listNodes[1];
        }


        return hair.next;
    }

    public ListNode[] myReverse(ListNode head, ListNode tail) {
        ListNode pre = tail.next;
        ListNode cur = head;
        while (pre != tail) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return new ListNode[]{tail, head};
    }

    @Test
    public void testReverse() {
        ListNode head = new ListNode(1, new ListNode(2));
        reverseKGroup(head, 2);
    }

    /**
     * 删除链表的倒数第n个节点
     *
     * @param head 链表头节点
     * @param n    倒数第n个节点
     * @return 头节点
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        ListNode left = head, right = head;
        int i = 0;
        while (i < n) {
            right = right.next;
            i++;
            if (right == null)
                return head.next;
        }
        while (right.next != null) {
            left = left.next;
            right = right.next;
        }
        left.next = left.next.next;
        return head;
    }

    /**
     * 删除排序链表中的重复元素 II
     * 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
     *
     * @param head head = [1,2,3,3,4,4,5]
     * @return [1, 2, 5]
     */
    public ListNode deleteDuplicates(ListNode head) {
        ListNode hair = new ListNode(0, head);
        ListNode pre = hair, cur = head;
        while (cur != null) {
            if (cur.next == null || cur.val != cur.next.val) {
                pre = cur;
                cur = cur.next;
                continue;
            }
            while (cur.next != null && cur.val == cur.next.val) {
                cur = cur.next;
            }
            pre.next = cur.next;
            cur = cur.next;
        }

        return hair.next;
    }

    /**
     * 旋转链表
     * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
     *
     * @param head head = [1,2,3,4,5],
     * @param k    k = 2
     * @return [4, 5, 1, 2, 3]
     */
    public ListNode rotateRight(ListNode head, int k) {
        ListNode newHead, left = head, right = head;
        int length = 0;
        while (left != null) {
            left = left.next;
            length++;
        }
        left = head;
        if (length == 0)
            return null;
        k %= length;
        if (k == 0)
            return head;
        int i = 0;
        while (i++ < k)
            right = right.next;
        while (right.next != null) {
            right = right.next;
            left = left.next;
        }
        newHead = left.next;
        left.next = null;
        right.next = head;

        return newHead;
    }

    /**
     * 分隔链表
     * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
     * 你应当 保留 两个分区中每个节点的初始相对位置。
     *
     * @param head head = [1,4,3,2,5,2],
     * @param x    x = 3
     * @return [1, 2, 2, 4, 3, 5]
     */
    public ListNode partition(ListNode head, int x) {
        ListNode lHead = null, rHead = null;
        ListNode left = null, right = null;
        while (head != null) {
            if (head.val < x) {
                if (lHead == null) {
                    lHead = head;
                    left = head;
                } else {
                    left.next = head;
                    left = left.next;
                }
            } else {
                if (rHead == null) {
                    rHead = head;
                    right = head;
                } else {
                    right.next = head;
                    right = right.next;
                }
            }
            head = head.next;
        }
        if (right != null)
            right.next = null;
        if (lHead == null) {
            return rHead;
        }
        left.next = rHead;
        return lHead;
    }

    public ListNode sortList(ListNode head) {
        return mergeSort(head, null);
    }

    public ListNode mergeSort(ListNode left, ListNode right) {
        if (left == null) {
            return left;
        }
        if (left.next == right) {
            left.next = null;
            return left;
        }

        ListNode slow = left, fast = left;
        while (fast != right) {
            slow = slow.next;
            fast = fast.next;
            if (fast != right)
                fast = fast.next;
        }

//        mergeSort(left, slow);
//        mergeSort(slow, right);
        return merge(mergeSort(left, slow), mergeSort(slow, right));
    }

    public ListNode merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        ListNode l = left, r = right;
        while (l != null && r != null) {
            if (l.val < r.val) {
                cur.next = l;
                l = l.next;
            } else {
                cur.next = r;
                r = r.next;
            }
            cur = cur.next;
        }
        if (l != null) cur.next = l;
        else if (r != null) cur.next = r;
        return dummy.next;
    }

    @Test
    public void testPo() {
        ListNode head = new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3))));
        sortList(head);
    }
}
